# Streaming Belief Propagation

This folder contains the algorithms from the NeurIPS 2021 submission 'Streaming Belief Propagation for Community Detection'.

## Compiling and Running the Code

One can simply compile all source files together using `g++ -O3 --std=c++17 *.cc` and run the resulting file with `./a.out`.

## Running Experiments in `main.cc`

`main.cc` contains a generic experiment on synthetic data from the Stochastic Block Model. Parameters
n, k, a, b, and alpha are given by the user. The experiment first generates an SBM graph with parameters
n, k, a and b. Next, it runs the streaming belief propagation algorithm from the paper, with the alpha-noised
ground truth labels as the side information, and a user-specified radius. Finally, the labels output by the algorithm
are compared to the ground truth labels using `OverlapEvaluate`.

The results of the paper on synthetic data can be recreated by setting the parameters in this experiment.

## Running Additional Experiments

Any specific experiment consists of an input graph (processed through a graph stream), a label propagation algorithm, and an evaluation metric.

To generate the input, first construct a `graph` object. Graphs from the stochastic block model can be randomly generated by constructing an `SBMGraph` object. Other ways of generating input graphs may be defined by the user. Once an input graph is constructed, make sure the adjacency lists are sorted using `Sort()`, and use it to construct a `GraphStream` object.

Next, construct any algorithm derived from `LabelPropagationAlgorithm`. The algorithms used in the paper, `bounded_distance_streaming_belief_propagation` and `side_info_ssbm`, are provided as examples. Generate a side information vector to be used by the algorithm. This may be done in a variety of ways, and is up to the user to implement. Use `LabelPropagationAlgorithm::Run()` to run the algorithm on the input graph and `LabelPropagationAlgorithm::GenerateClusters()` to retrieve the output.

Finally, construct an object inherited from `Evaluate`. `overlap_evaluate`, used in the paper, is provided as an example. Use the `()` operator to evaluate the output of the label propagation algorithm. Depending on the type of `Evaluate` object used, this may take additional arguments.

### Example experiment
    SBMGraph graph(100,2,10,3,92634862);
    graph.Sort();
    GraphStream graph_stream(&graph);

    PluralityVoting algorithm(); // Implemented by the user
    std::vector<int> side_info_vector = GenerateSideInfoVector();
    algorithm.Run(&graph_stream, &side_info_vector);
    std::vector<int> output = algorithm.GenerateClusters();

    OverlapEvaluate evaluate;
    double result = evaluate(output, graph.GetGroundTruthCommunities());
    std::cout << result;

Note that `SBMGraph` stores additionally a vector of ground truth community labels, which not all graphs have. This is then used as an additional argument for `evaluate`. `GenerateSideInfoVector` is a placeholder and the implementation of side information generation is left to the user.
